package com.qrpcw.algorithms;

import java.util.Arrays;

public class CountingSort {

	public static void main(String[] args) {
		CountingSort test = new CountingSort();
		int[] a = new int[]{3,6,4,1,3,4,1,4};
		int[] b = test.countingSort(a, 6);
		System.out.println(Arrays.toString(b));
	}
	public void countingSort(int[] A,int[] B,int k){
		int[] C = new int[k];
		for(int i=0; i<k; i++){
			C[i] = 0;
		}
		for(int j=0; j<A.length; j++){
				C[A[j]-1] = C[A[j]-1]+1;
		}
		System.out.println(Arrays.toString(C)); //202301
		for(int i=1; i<k; i++){
			C[i] = C[i] + C[i-1];
		}
		System.out.println(Arrays.toString(C)); //224778
		for(int j=A.length-1; j>=0; j--){
			B[C[A[j]-1]-1] = A[j];
			C[A[j]-1]= C[A[j]-1] - 1;
		}
	}
	
	public int[] countingSort(int[] A, int k){
		int[] B = new int[A.length];
		countingSort(A, B, k);
		return B;
	}
}
